package java_0220.leetcode;

//public class Num110_BalanceTree {
//    public boolean isBalanced(TreeNode root) {
//        if(root==null){
//            return true;
//        }
//        //判断当前以root为根节点的树是否满足平衡条件
//        int left=height(root.left);
//        int right=height(root.right);
//        int abs=Math.abs(left-right);//Math.abs()：计算两个数之间的距离值
//        if(abs>1){
//            return false;
//        }
//        //继续递归判断左树是否满足平衡并且右树是否满足平衡
//        return isBalanced(root.left)&&isBalanced(root.right);
//    }
//
//    private int height(TreeNode root) {
//        if(root==null){
//            return 0;
//        }
//        return 1+Math.max(height(root.left),height(root.right));
//    }
//}

import java.util.HashMap;
import java.util.Map;

/**
 * 记忆化搜索进行效率的优化
 */
public class Num110_BalanceTree {
    private Map<TreeNode,Integer> nodeIntegerMap=new HashMap<>();
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        //判断当前以root为根节点的树是否满足平衡条件
        int left=0;
        int right=0;
        if(nodeIntegerMap.containsKey(root.left)){
            //此时左树高度已经被计算过了，直接从Map中取出节点值对应高度
            left=nodeIntegerMap.get(root.left);
        }else{
            left=height(root.left);
            //同时将计算的高度存入Map中
            nodeIntegerMap.put(root.left,left);
        }
        if(nodeIntegerMap.containsKey(root.right)){
            //此时左树高度已经被计算过了，直接从Map中取出节点值对应高度
            right=nodeIntegerMap.get(root.right);
        }else{
            right=height(root.right);
            //同时将计算的高度存入Map中
            nodeIntegerMap.put(root.right,right);
        }
        int abs=Math.abs(left-right);//Math.abs()：计算两个数之间的距离值
        if(abs>1){
            return false;
        }
        //继续递归判断左树是否满足平衡并且右树是否满足平衡
        return isBalanced(root.left)&&isBalanced(root.right);
    }

    private int height(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+Math.max(height(root.left),height(root.right));
    }
}